package programmingpearls.samples;

import java.util.Arrays;
import java.util.Random;

public class BitmapSort {

    /** store bitmap in int[], every int has 32bits **/
    private final int BITSPERWORD = 32;

    /**
     * every int stores 32 numbers, right shift 5(or divide 32) to find the
     * index in bitmap. sample: 123456 is in bitmap[123456 >> SHIFT]
     */
    private final int SHIFT = 5;

    /**
     * 0x1F is 31, k & 0x1F can get the value equal to k % 32 use MASK to find
     * which bit represent number k in bitmap[k >> SHIFT]
     */
    private final int MASK = 0x1F;

    private int[] bitmap;
    private int totalNumbers;
    private int[] numbers;

    public BitmapSort(int totalNumbers) {
        this.totalNumbers = totalNumbers;
        bitmap = new int[1 + totalNumbers / BITSPERWORD];
        numbers = randomKNumbers(totalNumbers / 10, totalNumbers);
    }

    private void set(int index) {
        bitmap[index >> SHIFT] |= (1 << (index & MASK));
    }

    private void clr(int index) {
        bitmap[index >> SHIFT] &= ~(1 << (index & MASK));
    }

    private int valid(int index) {
        return bitmap[index >> SHIFT] & (1 << (index & MASK));
    }

    public void sort() {
        for (int i = 0; i < totalNumbers; i++) {
            clr(i);
        }

        for (int i = 0; i < numbers.length; i++) {
            set(numbers[i]);
        }

        for (int i = 0; i < totalNumbers; i++) {
            if (valid(i) != 0) {
                // System.out.println(i);
            }
        }
    }

    public int[] randomKNumbers(int k, int n) {

        int[] randomKNumbers = new int[k];
        Random random = new Random();

        int[] allNumbers = new int[n];
        for (int i = 0; i < n; i++) {
            allNumbers[i] = i;
        }

        for (int i = 0; i < k; i++) {
            int randomIndex = random.nextInt(n - i) + i;
            int temp = allNumbers[i];
            allNumbers[i] = allNumbers[randomIndex];
            allNumbers[randomIndex] = temp;
            randomKNumbers[i] = allNumbers[i];
        }

        return randomKNumbers;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int N = 10000000;
        BitmapSort bitmapSort = new BitmapSort(N);
        // int[] random = bitmapSort.randomKNumbers(100, 1000);
        //
        // for (int i : random) {
        // System.out.println(i);
        // }
        // System.out.println(random.length);
        long begin = System.currentTimeMillis();
        bitmapSort.sort();
        long used = System.currentTimeMillis() - begin;
        System.out.println(used + "ms");

        int[] numbers = bitmapSort.randomKNumbers(N / 10, N);
        begin = System.currentTimeMillis();
        Arrays.sort(numbers);
        used = System.currentTimeMillis() - begin;
        System.out.println(used + "ms");

    }

}
